Among, Common and Disjoint Constraints
Identifieur interne : 009840 ( Main/Exploration ); précédent : 009839; suivant : 009841Among, Common and Disjoint Constraints
Auteurs : Christian Bessiere [France] ; Emmanuel Hebrard [Australie] ; Brahim Hnich [Turquie] ; Zeynep Kiziltan [Italie] ; Toby Walsh [Australie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2006.
English descriptors
- KwdEn :
- Aaai press, Algorithm, Alldifferent constraint, Bessiere, Cardinality, Common constraint, Computational complexity, Constraint, Constraint propagation, Disjoint, Disjoint constraint, Disjoint constraints, Foreach, Global constraints, Hybrid, Hybrid support, Inlb, Integer, Integer variables, Lower bounds, Polynomial algorithm, Polynomial time, Propagation algorithm, Prune, Resp, Satisfying assignment, Second category, Special case, Tractable, Upper bounds.
- Teeft :
- Aaai press, Algorithm, Alldifferent constraint, Bessiere, Cardinality, Common constraint, Computational complexity, Constraint, Constraint propagation, Disjoint, Disjoint constraint, Disjoint constraints, Foreach, Global constraints, Hybrid, Hybrid support, Inlb, Integer, Integer variables, Lower bounds, Polynomial algorithm, Polynomial time, Propagation algorithm, Prune, Resp, Satisfying assignment, Second category, Special case, Tractable, Upper bounds.
Abstract
Abstract: Among, Common and Disjoint are global constraints useful in modelling problems involving resources. We study a number of variations of these constraints over integer and set variables. We show how computational complexity can be used to determine whether achieving the highest level of consistency is tractable. For tractable constraints, we present a polynomial propagation algorithm and compare it to logical decompositions with respect to the amount of constraint propagation. For intractable cases, we show in many cases that a propagation algorithm can be adapted from a propagation algorithm of a similar tractable one.
Url:
DOI: 10.1007/11754602_3
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000516
- to stream Istex, to step Curation: 000516
- to stream Istex, to step Checkpoint: 001474
- to stream Main, to step Merge: 00A302
- to stream Main, to step Curation: 009840
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Among, Common and Disjoint Constraints</title><author><name sortKey="Bessiere, Christian" sort="Bessiere, Christian" uniqKey="Bessiere C" first="Christian" last="Bessiere">Christian Bessiere</name></author><author><name sortKey="Hebrard, Emmanuel" sort="Hebrard, Emmanuel" uniqKey="Hebrard E" first="Emmanuel" last="Hebrard">Emmanuel Hebrard</name></author><author><name sortKey="Hnich, Brahim" sort="Hnich, Brahim" uniqKey="Hnich B" first="Brahim" last="Hnich">Brahim Hnich</name></author><author><name sortKey="Kiziltan, Zeynep" sort="Kiziltan, Zeynep" uniqKey="Kiziltan Z" first="Zeynep" last="Kiziltan">Zeynep Kiziltan</name></author><author><name sortKey="Walsh, Toby" sort="Walsh, Toby" uniqKey="Walsh T" first="Toby" last="Walsh">Toby Walsh</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:1B55E077CADB3A3DF188B41EBD3F2E06BAB76E7E</idno><date when="2006" year="2006">2006</date><idno type="doi">10.1007/11754602_3</idno><idno type="url">https://api.istex.fr/document/1B55E077CADB3A3DF188B41EBD3F2E06BAB76E7E/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000516</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000516</idno><idno type="wicri:Area/Istex/Curation">000516</idno><idno type="wicri:Area/Istex/Checkpoint">001474</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001474</idno><idno type="wicri:doubleKey">0302-9743:2006:Bessiere C:among:common:and</idno><idno type="wicri:Area/Main/Merge">00A302</idno><idno type="wicri:Area/Main/Curation">009840</idno><idno type="wicri:Area/Main/Exploration">009840</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Among, Common and Disjoint Constraints</title><author><name sortKey="Bessiere, Christian" sort="Bessiere, Christian" uniqKey="Bessiere C" first="Christian" last="Bessiere">Christian Bessiere</name><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>LIRMM CNRS, University of Montpellier</wicri:regionArea><wicri:noRegion>University of Montpellier</wicri:noRegion><wicri:noRegion>University of Montpellier</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Hebrard, Emmanuel" sort="Hebrard, Emmanuel" uniqKey="Hebrard E" first="Emmanuel" last="Hebrard">Emmanuel Hebrard</name><affiliation wicri:level="3"><country xml:lang="fr">Australie</country><wicri:regionArea>NICTA and UNSW, Sydney</wicri:regionArea><placeName><settlement type="city">Sydney</settlement><region type="état">Nouvelle-Galles du Sud</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Australie</country></affiliation></author><author><name sortKey="Hnich, Brahim" sort="Hnich, Brahim" uniqKey="Hnich B" first="Brahim" last="Hnich">Brahim Hnich</name><affiliation wicri:level="1"><country xml:lang="fr">Turquie</country><wicri:regionArea>Izmir University of Economics</wicri:regionArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Turquie</country></affiliation></author><author><name sortKey="Kiziltan, Zeynep" sort="Kiziltan, Zeynep" uniqKey="Kiziltan Z" first="Zeynep" last="Kiziltan">Zeynep Kiziltan</name><affiliation wicri:level="1"><country xml:lang="fr">Italie</country><wicri:regionArea>University of Bologna</wicri:regionArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Italie</country></affiliation></author><author><name sortKey="Walsh, Toby" sort="Walsh, Toby" uniqKey="Walsh T" first="Toby" last="Walsh">Toby Walsh</name><affiliation wicri:level="3"><country xml:lang="fr">Australie</country><wicri:regionArea>NICTA and UNSW, Sydney</wicri:regionArea><placeName><settlement type="city">Sydney</settlement><region type="état">Nouvelle-Galles du Sud</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Australie</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2006</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Aaai press</term><term>Algorithm</term><term>Alldifferent constraint</term><term>Bessiere</term><term>Cardinality</term><term>Common constraint</term><term>Computational complexity</term><term>Constraint</term><term>Constraint propagation</term><term>Disjoint</term><term>Disjoint constraint</term><term>Disjoint constraints</term><term>Foreach</term><term>Global constraints</term><term>Hybrid</term><term>Hybrid support</term><term>Inlb</term><term>Integer</term><term>Integer variables</term><term>Lower bounds</term><term>Polynomial algorithm</term><term>Polynomial time</term><term>Propagation algorithm</term><term>Prune</term><term>Resp</term><term>Satisfying assignment</term><term>Second category</term><term>Special case</term><term>Tractable</term><term>Upper bounds</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Aaai press</term><term>Algorithm</term><term>Alldifferent constraint</term><term>Bessiere</term><term>Cardinality</term><term>Common constraint</term><term>Computational complexity</term><term>Constraint</term><term>Constraint propagation</term><term>Disjoint</term><term>Disjoint constraint</term><term>Disjoint constraints</term><term>Foreach</term><term>Global constraints</term><term>Hybrid</term><term>Hybrid support</term><term>Inlb</term><term>Integer</term><term>Integer variables</term><term>Lower bounds</term><term>Polynomial algorithm</term><term>Polynomial time</term><term>Propagation algorithm</term><term>Prune</term><term>Resp</term><term>Satisfying assignment</term><term>Second category</term><term>Special case</term><term>Tractable</term><term>Upper bounds</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Among, Common and Disjoint are global constraints useful in modelling problems involving resources. We study a number of variations of these constraints over integer and set variables. We show how computational complexity can be used to determine whether achieving the highest level of consistency is tractable. For tractable constraints, we present a polynomial propagation algorithm and compare it to logical decompositions with respect to the amount of constraint propagation. For intractable cases, we show in many cases that a propagation algorithm can be adapted from a propagation algorithm of a similar tractable one.</div></front></TEI><affiliations><list><country><li>Australie</li><li>France</li><li>Italie</li><li>Turquie</li></country><region><li>Nouvelle-Galles du Sud</li></region><settlement><li>Sydney</li></settlement></list><tree><country name="France"><noRegion><name sortKey="Bessiere, Christian" sort="Bessiere, Christian" uniqKey="Bessiere C" first="Christian" last="Bessiere">Christian Bessiere</name></noRegion><name sortKey="Bessiere, Christian" sort="Bessiere, Christian" uniqKey="Bessiere C" first="Christian" last="Bessiere">Christian Bessiere</name></country><country name="Australie"><region name="Nouvelle-Galles du Sud"><name sortKey="Hebrard, Emmanuel" sort="Hebrard, Emmanuel" uniqKey="Hebrard E" first="Emmanuel" last="Hebrard">Emmanuel Hebrard</name></region><name sortKey="Hebrard, Emmanuel" sort="Hebrard, Emmanuel" uniqKey="Hebrard E" first="Emmanuel" last="Hebrard">Emmanuel Hebrard</name><name sortKey="Walsh, Toby" sort="Walsh, Toby" uniqKey="Walsh T" first="Toby" last="Walsh">Toby Walsh</name><name sortKey="Walsh, Toby" sort="Walsh, Toby" uniqKey="Walsh T" first="Toby" last="Walsh">Toby Walsh</name></country><country name="Turquie"><noRegion><name sortKey="Hnich, Brahim" sort="Hnich, Brahim" uniqKey="Hnich B" first="Brahim" last="Hnich">Brahim Hnich</name></noRegion><name sortKey="Hnich, Brahim" sort="Hnich, Brahim" uniqKey="Hnich B" first="Brahim" last="Hnich">Brahim Hnich</name></country><country name="Italie"><noRegion><name sortKey="Kiziltan, Zeynep" sort="Kiziltan, Zeynep" uniqKey="Kiziltan Z" first="Zeynep" last="Kiziltan">Zeynep Kiziltan</name></noRegion><name sortKey="Kiziltan, Zeynep" sort="Kiziltan, Zeynep" uniqKey="Kiziltan Z" first="Zeynep" last="Kiziltan">Zeynep Kiziltan</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 009840 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 009840 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:1B55E077CADB3A3DF188B41EBD3F2E06BAB76E7E
|texte= Among, Common and Disjoint Constraints
}}
| This area was generated with Dilib version V0.6.33. |  |